package search.twothreetree.arrayStyle;

import java.util.Arrays;

/**
 * 2-3树实现
 *
 * @author liangzj9624@163.com
 * @date 2020/4/4 下午10:23
 */
public class Tree23 {
    /**
     * 根结点初始为null
     */
    Node23 root;

    Tree23() {
        root = null;
    }

    public boolean isRoot(Node23 node23) {
        return root == node23;
    }

    /**
     * 插入数据
     *
     * @param data 要插入数据
     */
    public void add(int data) {
        if (root == null) {
            root = new Node23(data);
            root.datas[0] = data;
            return;
        }

        add(new Node23(data), root, null);
    }

    /**
     * 2-3树插入方法
     *
     * @param data        数据
     * @param currentNode 当前节点
     * @param parentNode  当前节点的双亲节点
     * @return
     */
    private Node23 add(Node23 data, Node23 currentNode, Node23 parentNode) {
        // 进行3节点拆分时会有节点返回给双亲节点进行插入
        Node23 returnNode;
        // 如果是叶子节点则插入数据
        if (currentNode.isLeaf()) {
            returnNode = currentNode.isFull() ? splitNode(data, currentNode) : updateNode(data, currentNode);
        } else {
            // 非叶子节点递归进入到叶子节点
            if (data.datas[0] == currentNode.datas[0]
                    || data.datas[0] == currentNode.datas[currentNode.dataSize - 1]) {
                throw new IllegalArgumentException("插入的数据不能重复");
            }

            // 接收子节点插入的返回值
            if (data.datas[0] < currentNode.datas[0]) {
                // 进入左节点
                returnNode = add(data, currentNode.childNodes[0], currentNode);
            } else if (data.datas[0] > currentNode.datas[currentNode.dataSize - 1]) {
                // 进入右节点
                returnNode = add(data, currentNode.childNodes[currentNode.dataSize], currentNode);
            } else {
                // 进入中间节点
                returnNode = add(data, currentNode.childNodes[1], currentNode);
            }
        }

        // 如果节点进行了分裂, 将数据返回当前节点的双亲节点进行插入操作
        if (returnNode == null || parentNode == null) {
            return null;
        } else {
            return parentNode.isFull() ? splitNode(returnNode, parentNode) : updateNode(returnNode, parentNode);
        }
    }

    /**
     * 升级2节点, 2节点升级没有节点需要插入双亲节点
     *
     * @param returnNode2  要插入的节点数据
     * @param currentNode2 要升级的节点
     * @return 不需要返回多余节点给双亲节点
     */
    private Node23 updateNode(Node23 returnNode2, Node23 currentNode2) {
        currentNode2.dataSize = 2;
        int[] datas = new int[currentNode2.dataSize];
        Node23[] childNodes = new Node23[currentNode2.dataSize + 1];

        // 分别处理来自左边的子树节点和右子树节点
        if (returnNode2.datas[0] > currentNode2.datas[0]) {
            // 来自右子树的节点
            datas[0] = currentNode2.datas[0];
            datas[1] = returnNode2.datas[0];
            childNodes[0] = currentNode2.childNodes[0];
            childNodes[1] = returnNode2.childNodes[0];
            childNodes[2] = returnNode2.childNodes[1];
        } else {
            // 来自左子树的结点
            datas[0] = returnNode2.datas[0];
            datas[1] = currentNode2.datas[0];
            //
            childNodes[0] = returnNode2.childNodes[0];
            childNodes[1] = returnNode2.childNodes[1];
            childNodes[2] = currentNode2.childNodes[1];
        }

        currentNode2.datas = datas;
        currentNode2.childNodes = childNodes;
        return null;
    }

    /**
     * 拆分一个3节点, 会形成一颗子树, 将这颗子树的根结点返回给当前节点的双亲节点, 做插入操作
     *
     * @param returnNode2  要插入的值
     * @param currentNode3 要拆分的节点
     * @return 返回拆分后的子树的根结点
     */
    private Node23 splitNode(Node23 returnNode2, Node23 currentNode3) {
        // 拆分后子树的根结点
        Node23 newRoot;

        // if分支从上到下分别表示左侧子树拆分、右侧子树拆分、中间子树拆分
        if (returnNode2.datas[0] < currentNode3.datas[0]) {
            newRoot = new Node23(currentNode3.datas[0]);
            // 拆分后子树的右子树
            Node23 rightChild = new Node23(currentNode3.datas[1]);
            rightChild.childNodes[1] = currentNode3.childNodes[2];
            rightChild.childNodes[0] = currentNode3.childNodes[1];
            // 拆分后的子树
            newRoot.childNodes[0] = returnNode2;
            newRoot.childNodes[1] = rightChild;
        } else if (returnNode2.datas[0] > currentNode3.datas[1]) {
            newRoot = new Node23(currentNode3.datas[1]);
            // 拆分后子树的左子树
            Node23 leftChild = new Node23(currentNode3.datas[0]);
            leftChild.childNodes[0] = currentNode3.childNodes[0];
            leftChild.childNodes[1] = currentNode3.childNodes[1];
            // 拆分后的子树
            newRoot.childNodes[0] = leftChild;
            newRoot.childNodes[1] = returnNode2;
        } else {
            newRoot = new Node23(returnNode2.datas[0]);
            // 拆分后的左子树
            Node23 leftChild = new Node23(currentNode3.datas[0]);
            leftChild.childNodes[0] = currentNode3.childNodes[0];
            leftChild.childNodes[1] = returnNode2.childNodes[0];
            // 拆分后的右子树
            Node23 rightChild = new Node23(currentNode3.datas[1]);
            rightChild.childNodes[0] = returnNode2.childNodes[1];
            rightChild.childNodes[1] = currentNode3.childNodes[2];
            // 拆分后的子树
            newRoot.childNodes[0] = leftChild;
            newRoot.childNodes[1] = rightChild;
        }

        // 如果当前节点是根结点, 则将分裂后的节点的根结点赋值给根节点
        if (this.isRoot(currentNode3)) {
            root = newRoot;
        }
        return newRoot;
    }

    /**
     * 中序遍历树的节点
     */
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    private void inorderTraversal(Node23 subTree) {
        if (subTree == null) {
            return;
        }
        inorderTraversal(subTree.childNodes[0]);
        System.out.println(Arrays.toString(subTree.datas));
        inorderTraversal(subTree.childNodes[1]);
        if (!subTree.isNode2()) {
            inorderTraversal(subTree.childNodes[2]);
        }
    }

}
